#include <stdio.h>
//图的应用之最短路径之弗洛伊德算法
#define MAXSIZE 100
#define MAX 0x10000
typedef struct 
{
    int vertex[MAXSIZE];//因为顶点是v0,v1这样的形式，所以我们只存下标，打印时写成"V%d"即可
    int edge[MAXSIZE][MAXSIZE];
    int vertex_num;
    int edge_num;
}mat_graph;
void creatgraph(mat_graph *g)
{
    g->vertex_num=9;
    g->edge_num=16;
    int i,j;
    for(i=0;i<g->vertex_num;i++)
    {
        g->vertex[i]=i;
    }
    for(i=0;i<g->vertex_num;i++)
    {
        for(j=0;j<g->vertex_num;j++)
        {
            if(i==j)
            g->edge[i][j]=0;
            else
            g->edge[i][j]=MAX;
        }
    }
    g->edge[0][1]=1;
    g->edge[0][2]=5;
    g->edge[1][2]=3;
    g->edge[1][3]=7;
    g->edge[1][4]=5;
    g->edge[2][4]=1;
    g->edge[2][5]=7;
    g->edge[3][4]=2;
    g->edge[3][6]=3;
    g->edge[4][5]=3;
    g->edge[4][6]=6;
    g->edge[4][7]=9;
    g->edge[5][7]=5;
    g->edge[6][7]=2;
    g->edge[6][8]=7;
    g->edge[7][8]=4;
    for(i=0;i<g->vertex_num;i++)
    {
        for(j=0;j<i;j++)
        {
            g->edge[i][j]=g->edge[j][i];
        }
    }
}
void floyd(mat_graph *g)
{
    int D[MAXSIZE][MAXSIZE];
    int P[MAXSIZE][MAXSIZE];
    //初始化
    int i,j,k;
    for(i=0;i<g->vertex_num;i++)
    {
        for(j=0;j<g->vertex_num;j++)
        {
            D[i][j]=g->edge[i][j];
            P[i][j]=j;
        }
    }
    //i:中转顶点 j:起始顶点 k:终止顶点
    for(i=0;i<g->vertex_num;i++)  //中转顶点必须放在循环最外层 P210
    {
        for(j=0;j<g->vertex_num;j++)  //进到边数组每一行
        {
            for(k=0;k<g->vertex_num;k++)   //进到边数组每一行中的每一列
            {
                if(D[j][k]>D[j][i]+D[i][k])
                {
                    D[j][k]=D[j][i]+D[i][k];
                    P[j][k]=P[j][i]; //要根据中转点找到下一个中转点
                }
            }
        }
    }
    //打印:每一个顶点到其他顶点的最短路径（v小->v大）
    for(i=0;i<g->vertex_num;i++)  
    {
        for(j=i+1;j<g->vertex_num;j++)
        {
            printf("v%d->v%d weight:%d ",i,j,D[i][j]);
            k=P[i][j];
            printf("path:v%d->",i); //打印起点
            while(k!=j)             //打印中转点
            {
                printf("v%d->",k);
                k=P[k][j];
            }
            printf("v%d\n",j);     //打印终点
        }
        printf("\n");
    }
}
int main()
{
    mat_graph g;
    creatgraph(&g);
    floyd(&g);
    return 0;
}
/*
v0->v1 weight:1 path:v0->v1
v0->v2 weight:4 path:v0->v1->v2
v0->v3 weight:7 path:v0->v1->v2->v4->v3
v0->v4 weight:5 path:v0->v1->v2->v4
v0->v5 weight:8 path:v0->v1->v2->v4->v5
v0->v6 weight:10 path:v0->v1->v2->v4->v3->v6
v0->v7 weight:12 path:v0->v1->v2->v4->v3->v6->v7
v0->v8 weight:16 path:v0->v1->v2->v4->v3->v6->v7->v8

v1->v2 weight:3 path:v1->v2
v1->v3 weight:6 path:v1->v2->v4->v3
v1->v4 weight:4 path:v1->v2->v4
v1->v5 weight:7 path:v1->v2->v4->v5
v1->v6 weight:9 path:v1->v2->v4->v3->v6
v1->v7 weight:11 path:v1->v2->v4->v3->v6->v7
v1->v8 weight:15 path:v1->v2->v4->v3->v6->v7->v8

v2->v3 weight:3 path:v2->v4->v3
v2->v4 weight:1 path:v2->v4
v2->v5 weight:4 path:v2->v4->v5
v2->v6 weight:6 path:v2->v4->v3->v6
v2->v7 weight:8 path:v2->v4->v3->v6->v7
v2->v8 weight:12 path:v2->v4->v3->v6->v7->v8

v3->v4 weight:2 path:v3->v4
v3->v5 weight:5 path:v3->v4->v5
v3->v6 weight:3 path:v3->v6
v3->v7 weight:5 path:v3->v6->v7
v3->v8 weight:9 path:v3->v6->v7->v8

v4->v5 weight:3 path:v4->v5
v4->v6 weight:5 path:v4->v3->v6
v4->v7 weight:7 path:v4->v3->v6->v7
v4->v8 weight:11 path:v4->v3->v6->v7->v8

v5->v6 weight:7 path:v5->v7->v6
v5->v7 weight:5 path:v5->v7
v5->v8 weight:9 path:v5->v7->v8

v6->v7 weight:2 path:v6->v7
v6->v8 weight:6 path:v6->v7->v8

v7->v8 weight:4 path:v7->v8
*/